//
//  AVLTree.swift
//  DataStructureAndAlgorithm
//
//  Created by icemelon on 2021/8/8.
//

import Foundation


/// 每一个几点的平衡因子只可能是1 0 -1， 每一个节点的左右子树高度差不超过1  搜索添加删除的时间复杂度为O(logj)
class AVLTree<T: Comparable> : BinarySearchTree<T> {
    //添加之后恢复平衡  添加可能导致所有的祖先节点失衡例如1,2,3,4,5这样添加。但是只需要每次添加后让最低失衡的点恢复平衡，整棵树就一直是平衡的
    override func afterAdd(node: Node<T>) {
        /* 添加后的集中情况(中序遍历为递增的情况说明) 添加的节点为node简称n，父节点为parent简称p，祖父节点为grandparent简称g
         1.递减添加元素 如5，4，3，2 称为LL，需要对g右单旋 可以理解为将p提上去
         2.递增添加元素 如1，2，3，4 称为RR，需要对g左单旋 可以理解为将p提上去
         3.减增添加元素 如5，2，4 称为LR，需要对p左单旋 然后对g右单旋 可以理解为将n提上去2次
         4.增减添加元素 如5，8，6 称为RL，需要对p右单旋 然后对g左单旋 可以理解为将n提上去2次
         LL等第一个指的是 p 第二个指的是n
         修复之后要维护内容 parent和child等 先后恢复低位节点的高度
         */
        var nodeParent = node.parent
        
        while nodeParent != nil {
            //判断是否失衡
            if nodeParent!.isBalance() {
                //更新高度
                nodeParent?.updateHeight()
                nodeParent = nodeParent?.parent
            }
            else {
                //恢复平衡
                reBalance(g: nodeParent!)
                return
            }
        }
    }
    
    
    /// 删除会导致父节点或祖先节点失衡  只有一个失衡   但是  恢复平衡后可能导致更高额节点失衡 需要O（logn）次数调整
    override func afterRemove(node: BinaryTree<T>.Node<T>) {
        var nodeParent = node.parent
        while nodeParent != nil {
            if nodeParent!.isBalance() {
                node.updateHeight()
            }
            else {
                reBalance(g: nodeParent!)
            }
            nodeParent = nodeParent?.parent
        }
    }
    
    /// 添加失衡点为grandparent
    
    /// <#Description#>
    /// - Parameters:
    ///   - g: 失衡的节点
    func reBalance(g: Node<T>) {
        
        let parent = g.tallerChild
        let node = parent.tallerChild
        
        if parent.isLeft() { //L
            if node.isLeft() { //LL
                rotateRight(n: g)

            }
            else if node.isRight() {//LR
                rotateLeft(n: parent)
                
                rotateRight(n: g)
            }
        }
        else if parent.isRight() {//R
            if node.isLeft() { //RL
                rotateRight(n: parent)
                rotateLeft(n: g)
            }
            else if node.isRight() {//RR
                rotateLeft(n: g)
            }
        }
    }
    
    func rotateLeft(n: Node<T>) {//传入将要旋转的节点
        
        let toBeRotedNode = n //将要旋转的节点
        let toBeRisedNode = toBeRotedNode.right!//将要上提的节点
        let childTreeNode = toBeRisedNode.left//将要上提的节点 的子树 的节点
        
        toBeRotedNode.right = childTreeNode
        toBeRisedNode.left = toBeRotedNode
        
        afterRoated(toBeRotedNode: toBeRotedNode, toBeRisedNode: toBeRisedNode, childTreeNode: childTreeNode)
    }
    
    func rotateRight(n: Node<T>) {//传入将要旋转的节点
        
        let toBeRotedNode = n //将要旋转的节点
        let toBeRisedNode = toBeRotedNode.left!//将要上提的节点
        let childTreeNode = toBeRisedNode.right//将要上提的节点 的子树 的节点
        
        toBeRotedNode.left = toBeRisedNode.right
        toBeRisedNode.right = toBeRotedNode
        
        afterRoated(toBeRotedNode: toBeRotedNode, toBeRisedNode: toBeRisedNode, childTreeNode: childTreeNode)
    }
    
    func afterRoated(toBeRotedNode: Node<T>, toBeRisedNode: Node<T>, childTreeNode: Node<T>?) {
        
        //将要上提的节点 嫁接到原来的树中
        if toBeRotedNode.isRight() {
            toBeRotedNode.parent?.right = toBeRisedNode
        }
        else if toBeRotedNode.isLeft() {
            toBeRotedNode.parent?.left = toBeRisedNode
        }
        else {
            root = toBeRisedNode
        }
        
        childTreeNode?.parent = toBeRotedNode
        
        toBeRisedNode.parent = toBeRotedNode.parent
        toBeRotedNode.parent = toBeRisedNode
        
        
        toBeRotedNode.updateHeight()
        toBeRisedNode.updateHeight()
    }
}

extension AVLTree {
    class func testAVLTree() {
        let data = [26, 27, 13, 12, 9, 3, 28, 25, 2, 29, 1, 4, 8, 18, 15, 22, 6]
//        let data = [1,2,3,4,5,6,7,8,9,10, 11, 12, 14]
//        let data = [10, 9, 8, 7, 6 , 5 ,4, 3, 2, 1]
        
//        let data = [9, 7, 19, 14, 17, 10, 20, 16, 18, 13, 11, 2, 12, 15, 8]
        let tree = AVLTree<Int>(com: .orderedAscending)
        for item in data {
            tree.add(element: item)
//            tree.printTree()
        }
        
        tree.remove(element: 9)
        tree.remove(element: 8)
        tree.remove(element: 4)
        
        tree.remove(element: 6)
        tree.remove(element: 22)
        tree.remove(element: 25)
        tree.printTree()
        
//        let removeData = [4, 9, 11, 1]
//        for item in removeData {
//            tree.remove(element: item)
//            tree.printTree()
//        }
 
//        tree.traverse(by: .Preord)
//        tree.traverse(by: .Inorder)
//        tree.traverse(by: .Postorder)
//        tree.traverse(by: .LevelOrder)
        
//        tree.traverse(by: .LevelOrder)  { item in
//            print(item)
//        }
   
    }
}
